/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.vijos;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/4/25
 */
//采药
//山洞里有一些不同的草药
//采每一株都需要一些时间，每一株也有它自身的价值
//让采到的草药的总价值最大
//输入格式:
//第一行有两个整数T和M
//T代表总共能够用来采药的时间
//M代表山洞里的草药的数目
//接下来的M行分别表示采摘某株草药的时间和这株草药的价值
//输出格式：
//输出包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

//动态规划算法的一般模式：
//① 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。（在划分阶段时，注意有序或可排序）
//② 确定状态和状态变量：将问题发展到各个阶段时所处的各种情况用不同状态表示出来；
//③ 确定决策并写出状态转移方程：一般是根据相邻两个阶段各状态之间的关系来确定决策；
//④ 寻找终止条件：给出的状态转移方程是一个递推式，必须有一个递推的终止条件；

//1.首先以采摘的时间为阶段。
//2、确立状态及状态变量：dp[t]
//3、决策：如果采摘第i种药品获得的价值大于不采摘的情况，最大价值等于采摘第i种药品获得的价值；反之，最大价值等于不采摘第i种药品获得的价值。
//4、状态转移方程：max[t]=max{value[i] + max[t-time[i]],max[t-1]}
public class P15_1_1104 {


    public static int test(int t, int[][] input) {
        int[] dp = new int[t + 1];
        List<Info> infos = new ArrayList<>();
        for (int i = 0; i < input.length; i++) {
            int time = input[i][0];
            if (time <= t) {
                infos.add(new Info().setTime(input[i][0]).setValue(input[i][1]));
            }
        }
        for (int i = 0; i < infos.size(); i++) {
            Info info = infos.get(i);
            for(int j = t; j >= info.getTime(); j--) {
                if(dp[j] < dp[j - info.getTime()] + info.getValue()) {
                    dp[j] = dp[j - info.getTime()] + info.getValue();
                }
            }
        }
        int max = 0;
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        return max;
    }

    public static class Info {
        int time;
        int value;

        public int getTime() {
            return time;
        }

        public Info setTime(int time) {
            this.time = time;
            return this;
        }

        public int getValue() {
            return value;
        }

        public Info setValue(int value) {
            this.value = value;
            return this;
        }
    }

    public static void main(String[] args) {
        System.out.println(test(70, new int[][] {
                {71, 100},
                {60, 20},
                {3, 2},
                {3, 3},
                {3, 4},
                {3, 5}
        }));
    }
}
